package Bi_Tree.level_traversal;

import Bi_Tree.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

//二叉树的最小深度
public class lc111 {
    public int minDepth(TreeNode root) {
        //递归法
        //输入输出： 根节点；最小深度
        //递归终止条件：节点为空
        if(root==null){
            return 0;
        }
        //单层递归逻辑
        int minleft=minDepth(root.left);
        int minright=minDepth(root.right);
        if (root.left == null&&root.right!=null) {
            return minright + 1;
        }
        if (root.right == null&&root.left!=null) {
            return minleft + 1;
        }
        // 左右结点都不为null
        return Math.min(minleft, minright) + 1;
    }

    public int MinDepth(TreeNode root){
        //层次遍历   有问题
        Queue<TreeNode> queue=new LinkedList<>();
        TreeNode node=root;
        queue.offer(node);
        int level=0;
        if(root==null){
            return 0;
        }
        while (!queue.isEmpty()){
            int len= queue.size();
            level++;
            while (len>0){
                boolean left=false;
                boolean right=false;
                if(node.left!=null) {
                    queue.offer(node.left);
                    left=true;
                }
                if(node.right!=null) {
                    queue.offer(node.right);
                    right=true;
                }
                if(!right&&!left){
                    return level;
                }
                len--;
            }
        }
        return level;
    }
}
